1. Field of the Invention
The present invention relates to prime number deriving method and apparatus allowing derivation of prime numbers of arbitrary ranks.
2. Description of the Related Art
It is an extremely difficult work from theoretical and arithmetic viewpoints to exclusively select only prime numbers with definite ranks from a group of numbers having a diversity of properties, which will require processing of electronic computers. Nevertheless, by virtue of the difficulty of selection, the prime numbers are often used in beneficial processes in the industrial fields, including use as ciphers for message authentication, user validation, etc.
For this reason, various prime number deriving methods and verifying methods have hitherto been proposed. Known are for example methods of deriving prime numbers by executing a modular calculation having its basis in the finite region expressed by GF (2n) as Galois field through determination of two prime numbers by RSA method or through use of error correction parameters on modular operations by Montgomery method, and by executing a modular calculation by modular reduction in accordance with Montgomery method (see Japanese Patent Nos. 2,722,411, 2,722,412, 2,722,413, and France Patent No. 2,679,054).
Without exceptions, however, the conventional methods have derived prime numbers through extremely complex processing and processes, requiring an elongated processing time for the derivation, and have failed to achieve simple derivation of prime numbers of arbitrary ranks.
It is therefore the object of the present invention to derive prime numbers through effective processing and steps on the basis of a high degree of theory, to thereby remarkably reduce the processing time required for the derivation and to enable prime numbers of arbitrary ranks to be derived in a simple manner.